home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / TEMP / GNU / bison / MidRuleAct < prev    next >
Text File  |  1995-06-28  |  6KB  |  154 lines
  1. Mid-Rule Actions
  2. Previous: <Action Types=>ActionType> * Next: <Declarations=>Declaratio> * Up: <Semantics=>Semantics>
  3.  
  4. #Wrap on
  5. {fH4}Actions in Mid-Rule{f}
  6.  
  7. Occasionally it is useful to put an action in the middle of a rule.
  8. These actions are written just like usual end-of-rule actions, but they
  9. are executed before the parser even recognizes the following components.
  10.  
  11. A mid-rule action may refer to the components preceding it using
  12. {fCode}${fStrong}n{f}{f}, but it may not refer to subsequent components because
  13. it is run before they are parsed.
  14.  
  15. The mid-rule action itself counts as one of the components of the rule.
  16. This makes a difference when there is another action later in the same rule
  17. (and usually there is another at the end): you have to count the actions
  18. along with the symbols when working out which number {fStrong}n{f} to use in
  19. {fCode}${fStrong}n{f}{f}.
  20.  
  21. The mid-rule action can also have a semantic value.  The action can set
  22. its value with an assignment to {fCode}$${f}, and actions later in the rule
  23. can refer to the value using {fCode}${fStrong}n{f}{f}.  Since there is no symbol
  24. to name the action, there is no way to declare a data type for the value
  25. in advance, so you must use the {fEmphasis}$<…>{f} construct to specify a
  26. data type each time you refer to this value.
  27.  
  28. There is no way to set the value of the entire rule with a mid-rule
  29. action, because assignments to {fCode}$${f} do not have that effect.  The
  30. only way to set the value for the entire rule is with an ordinary action
  31. at the end of the rule.
  32.  
  33. Here is an example from a hypothetical compiler, handling a {fCode}let{f}
  34. statement that looks like {fEmphasis}let ({fStrong}variable{f}) {fStrong}statement{f}{f} and
  35. serves to create a variable named {fStrong}variable{f} temporarily for the
  36. duration of {fStrong}statement{f}.  To parse this construct, we must put
  37. {fStrong}variable{f} into the symbol table while {fStrong}statement{f} is parsed, then
  38. remove it afterward.  Here is how it is done:
  39.  
  40. #Wrap off
  41. #fCode
  42. stmt:   LET '(' var ')'
  43.                 \{ $<context>$ = push\_context ();
  44.                   declare\_variable ($3); \}
  45.         stmt    \{ $$ = $6;
  46.                   pop\_context ($<context>5); \}
  47. #f
  48. #Wrap on
  49.  
  50. As soon as {fEmphasis}let ({fStrong}variable{f}){f} has been recognized, the first
  51. action is run.  It saves a copy of the current semantic context (the
  52. list of accessible variables) as its semantic value, using alternative
  53. {fCode}context{f} in the data-type union.  Then it calls
  54. {fCode}declare\_variable{f} to add the new variable to that list.  Once the
  55. first action is finished, the embedded statement {fCode}stmt{f} can be
  56. parsed.  Note that the mid-rule action is component number 5, so the
  57. {fEmphasis}stmt{f} is component number 6.
  58.  
  59. After the embedded statement is parsed, its semantic value becomes the
  60. value of the entire {fCode}let{f}-statement.  Then the semantic value from the
  61. earlier action is used to restore the prior list of variables.  This
  62. removes the temporary {fCode}let{f}-variable from the list so that it won't
  63. appear to exist while the rest of the program is parsed.
  64.  
  65. Taking action before a rule is completely recognized often leads to
  66. conflicts since the parser must commit to a parse in order to execute the
  67. action.  For example, the following two rules, without mid-rule actions,
  68. can coexist in a working parser because the parser can shift the open-brace
  69. token and look at what follows before deciding whether there is a
  70. declaration or not:
  71.  
  72. #Wrap off
  73. #fCode
  74. compound: '\{' declarations statements '\}'
  75.         | '\{' statements '\}'
  76.         ;
  77. #f
  78. #Wrap on
  79.  
  80. But when we add a mid-rule action as follows, the rules become nonfunctional:
  81.  
  82. #Wrap off
  83. #fCode
  84. compound: \{ prepare\_for\_local\_variables (); \}
  85.           '\{' declarations statements '\}'
  86.         | '\{' statements '\}'
  87.         ;
  88. #f
  89. #Wrap on
  90.  
  91. Now the parser is forced to decide whether to run the mid-rule action
  92. when it has read no farther than the open-brace.  In other words, it
  93. must commit to using one rule or the other, without sufficient
  94. information to do it correctly.  (The open-brace token is what is called
  95. the {fUnderline}look-ahead{f} token at this time, since the parser is still
  96. deciding what to do about it.  \*Note <Look-Ahead=>LookAhead>: Look-Ahead Tokens.)
  97.  
  98. You might think that you could correct the problem by putting identical
  99. actions into the two rules, like this:
  100.  
  101. #Wrap off
  102. #fCode
  103. compound: \{ prepare\_for\_local\_variables (); \}
  104.           '\{' declarations statements '\}'
  105.         | \{ prepare\_for\_local\_variables (); \}
  106.           '\{' statements '\}'
  107.         ;
  108. #f
  109. #Wrap on
  110.  
  111. But this does not help, because Bison does not realize that the two actions
  112. are identical.  (Bison never tries to understand the C code in an action.)
  113.  
  114. If the grammar is such that a declaration can be distinguished from a
  115. statement by the first token (which is true in C), then one solution which
  116. does work is to put the action after the open-brace, like this:
  117.  
  118. #Wrap off
  119. #fCode
  120. compound: '\{' \{ prepare\_for\_local\_variables (); \}
  121.           declarations statements '\}'
  122.         | '\{' statements '\}'
  123.         ;
  124. #f
  125. #Wrap on
  126.  
  127. Now the first token of the following declaration or statement,
  128. which would in any case tell Bison which rule to use, can still do so.
  129.  
  130. Another solution is to bury the action inside a nonterminal symbol which
  131. serves as a subroutine:
  132.  
  133. #Wrap off
  134. #fCode
  135. subroutine: \/\* empty \*\/
  136.           \{ prepare\_for\_local\_variables (); \}
  137.         ;
  138.  
  139.  
  140. compound: subroutine
  141.           '\{' declarations statements '\}'
  142.         | subroutine
  143.           '\{' statements '\}'
  144.         ;
  145. #f
  146. #Wrap on
  147.  
  148. Now Bison can execute the action in the rule for {fCode}subroutine{f} without
  149. deciding which rule for {fCode}compound{f} it will eventually use.  Note that
  150. the action is now at the end of its rule.  Any mid-rule action can be
  151. converted to an end-of-rule action in this way, and this is what Bison
  152. actually does to implement mid-rule actions.
  153.  
  154.